/**
 * @author 徐楠
 * @date 2022/5/14 8:48
 * @version 1.0
 */

package com.xunan.likou;

public class MagicString {
    public static void main(String[] args) {
        magicalString(6);
    }

    /**
     * 字符串 S 的前几个元素如下：S = "1221121221221121122 ......"，我们来研究一下字符串 S 是如何生成的。
     *
     * 假设字符串 S 第一个字符为 1 时，那么第二个字符是什么呢？
     * 我们不妨假设还存在一个字符串 A 它决定字符串 S 中连续字符的个数且字符串 A 等于字符串 S。
     * 所以当字符串 S 的第一个字符为 1 时，字符串 A 的第一个字符也为 1。
     * 因为字符串 A 决定字符串 S 中连续字符的个数，所以字符串 S 的第一个字符最多能有 1 个。
     * 因为字符串 S 只包含 '1' 和 '2'且第一个字符最多能有 1 个，所以第二个字符一定为 2。
     * S = 12 所以 A = 12，因为 A 的第二个字符为 2，所以 S 中第二个字符应该出现两次，S = 122。
     * S = 122 所以 A = 122，因为 A 的第三个字符为 2，所以 S 的下一个字符也应该出现两次，S = 12211。
     * S = 12211 所以 A = 12211，因为 A 的第四个字符为 1，所以 S 的下一个字符出现一次，S = 122112。
     * ...
     * 之后只需生成一个长度为 n 的字符串 S，统计其中 1 的个数即可。
     * 题目中的示例的解释写错了，前 6 个元素应该是 122112，它只给了 5 个元素。
     *
     */
    public static int magicalString(int n) {
        // index 表示字符串 A 的索引，根据该索引的字符生成指定个数的字符，
        int index = 1;
        StringBuilder s = new StringBuilder();
        // 第一个字符为 1
        s.append(1);
        while (s.length() < n) {
            // 因为需要根据字符串 A，来确定在字符串 S 生成字符的个数
            // 所以当字符串 A 越界时，则根据前一个字符进行生成
            if (index == s.length()) {
                // 如果前一个字符为 1，则生成 22。
                s.append(s.charAt(s.length() - 1) == '1' ? 22 : 1);
                index++;
            } else {
                // 如果字符串 A 没有越界，则字符串 A 决定生成字符的个数。
                // 而字符串 S 的最后一个字符决定生成的字符是 1 还是 2
                if (s.charAt(s.length() - 1) == '1') {
                    s.append(s.charAt(index++) == '1' ? 2 : 22);
                } else {
                    s.append(s.charAt(index++) == '1' ? 1 : 11);
                }
            }
        }
        // count 统计 1 的个数
        int count = 0;
        // 遍历字符串统计 1 的个数
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                count++;
            }
        }
        return count;
    }

}
